package com.kongge.algorithm.demo;

import java.util.Stack;

/**
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数，在该栈中，调用min,push及pop的时间复杂度都是O(1)。
 * @author kongge
 *
 */
public class MinStackTest implements IAlgorithm{

	public void execute() {
		int[] arr = {3, 4, 2, 5, 1};
		MinStack minStack = new MinStack();
		for (int i = 0; i < arr.length; i++) {
			minStack.push(arr[i]);
		}
		while (minStack.size() != 0) {
			System.out.println("min is " + minStack.min());
			minStack.pop();
		}
	}
	/**
	 * 定义一个辅助栈，里面存储数据栈的最小元素，每次数据入栈的时候，如果数据比辅助栈的栈顶小，辅助栈就将该数压栈，否则将辅助栈栈顶再次压栈。
	 * @author kongge
	 *
	 */
	private class MinStack {
		private Stack<Integer> dataStack;
		private Stack<Integer> minStack;
		
		public MinStack() {
			dataStack = new Stack<Integer>();
			minStack = new Stack<Integer>();
		}
		
		private void push(int number) {
			dataStack.push(number);
			if (minStack.size() == 0 || number < minStack.peek()) {
				minStack.push(number);
			} else {
				minStack.push(minStack.peek());
			}
		}
		
		private Integer pop() {
			minStack.pop();
			return dataStack.pop();
		}
		
		private Integer min() {
			return minStack.peek();
		}
		
		private int size() {
			return dataStack.size();
		}
	}
}
